############################################################
# 有监督学习
############################################################
import numpy as np


def minkowski(x, y, p):
    """
    # 求x与y的闵氏距离
    """
    return np.sum(np.abs(x-y)**p)**(1/p)


def findindex(x, ls):
    """
    # 获取x插入有序列表ls后所在位置
    """
    ls.append(x)
    ls.sort()
    return ls.index(x)


def kNN(k, x, ls, categoryls, p=2):
    """
    # kNN分类算法
    # k为预设近邻数
    # x为待预测样本
    # ls为已分类样本坐标序列
    # categoryls为已分类样本类别序列
    # p为闵氏距离度量的阶数
    """
    k_list_pointer = []     # 暂存与x最近的k个样本的下标
    k_list_distance = []    # 暂存与x最近的k个样本的距离
    for i in range(k):
        # 对最初k个样本排序
        tmp_distance = minkowski(ls[i], x, p)
        ptr = findindex(tmp_distance, k_list_distance)
        k_list_pointer.insert(ptr, i)
    for i in range(k, len(ls)):
        # 若下一个已分类样本与x的距离小于k_list_distance中距离则更新k_list_pointer
        tmp_distance = minkowski(ls[i], x, p)
        ptr = findindex(tmp_distance, k_list_distance)
        if ptr != k:
            k_list_pointer.insert(ptr, i)
            k_list_pointer.pop()
        k_list_distance.pop()
    for i in range(k):
        k_list_pointer[i] = categoryls[k_list_pointer[i]]
    return max(k_list_pointer, key=k_list_pointer.count)
